#!/usr/bin/env python
import sys
import numpy as np
from profilehooks import profile
import util

class Bucket(object):
    def __init__(self, pBucket, nBucket, child, value=1):
        self.value = value
        self.next = nBucket if nBucket != None else self
        if self.next != self : self.next.prev = self
        self.prev = pBucket if pBucket != None else self
        if self.prev.next != self : self.prev.next = self
        self.firstChild = child
        self.firstChild.next = child
        self.firstChild.prev = child
        self.firstChild.parent = self

    def __str__(self):
        result = str("%s:[%s" % (self.value, self.firstChild))
        tmp = self.firstChild.next

        while (tmp != self.firstChild):
            result += ",%s" % str(tmp)
            tmp = tmp.next
        result += "]\n"
        return str(result)

    def insert(self, counter) :
        counter.parent = self
        counter.prev = self.firstChild.prev
        counter.next = self.firstChild
        counter.prev.next = counter
        self.firstChild.prev = counter
        if self.firstChild.next == self :
            self.firstChild.next = counter

    def remove(self, counter):
        if (counter.prev == counter and counter.next == counter) :
            return True
        else :
            counter.prev.next = counter.next
            counter.next.prev = counter.prev
            if (self.firstChild == counter) :
                #print "FC.n:", self.firstChild
                self.firstChild = self.firstChild.next
            return False

    def isEmpty(self) :
        return self.firstChild == None

class Counter(object):
    def __init__(self, element, parent):
        self.element = element
        self.prev = self
        self.next = self
        self.parent = parent

    def assign_bucket(self, bucket) :
        self.parent = bucket
        bucket.insert(self)

    def __str__(self) :

        return str(self.element)

class Stream_Summary(object):
    def __init__(self, k):
        self.elements = {}
        self.size = k
        self.min = None #somehow init with empty bucket

    def __str__(self):
        result = str(self.min)
        tmp = self.min.next

        while (tmp != self.min and tmp != None):
            result += str(tmp) + " "
            tmp = tmp.next

        return str(result)

    def insert(self, element):
        if element in self.elements :
            #print "debug: %s already monitored" % element
            counter = self.elements[element]
            bucket = counter.parent

            #print "bucket.nmet", str(bucket.next)
            #print "bucket:", str(bucket)
            #print "bucket.prev", str(bucket.prev)

            #print "self.min", str(self.min)

            if bucket.next != None and bucket.next.value == bucket.value + 1:
                #print "debug: incremented count of %s equals next bucket" % element
                # incremented count of element equals next bucket

                remove =  bucket.remove(counter)


                # check if parent bucket will be empty after reassigning element
                if remove :


                    #update bucket next to bucket.prev
                    if bucket.prev == bucket.next :
                        # only two buckets
                        bucket.prev.next = bucket.next
                        bucket.next.prev = bucket.prev
                    else :
                        bucket.prev.next = bucket.next
                        bucket.next.prev = bucket.prev

                    # bucket.next.next = bucket.next
                    #print "remove parent bucket"
                    bucket.next.insert(counter)
                    if self.min == bucket :
                        #print "updating self.min"
                        self.min = bucket.next
                    bucket = None


                else :
                    bucket.next.insert(counter)

            else :
                #print "incremented count of element is not equal to next bucket. inserting new bucket"
                # incremented count of element is not equal to next bucket --> insert new bucket
                remove = bucket.remove(counter)
                new_bucket = None
                if  remove :


                    new_bucket = Bucket(bucket.prev, bucket.next, counter, bucket.value + 1)
                    bucket.prev.next = new_bucket
                    bucket.next.prev = new_bucket
                    #print "#############################"
                    #print "remove parent bucket"
                    if self.min == bucket :
                        #print "self.min == bucket"
                        self.min = new_bucket
                        #print str(self.min)

                    bucket = None
                else :
                    new_bucket = Bucket(bucket, bucket.next, counter, bucket.value + 1)
                    bucket.next = new_bucket
                    bucket.prev = new_bucket if bucket.prev == bucket else bucket.prev

                counter.assign_bucket(new_bucket)

        elif len(self.elements) < self.size:
            #print "element %s not monitered. Stream Summary not full" % element
            # element not monitered. Stream Summary not full --> insert new bucket
            counter = Counter(element, None)

            if self.min == None :
                #print "initial case "
                # handles initial case where StreamSummary is empty
                new_bucket = Bucket(None, None, counter)
                self.min = new_bucket

            elif self.min.value == 1 :
                #print "add element to min bucket"
                self.min.insert(counter)
            else :
                #print " new bucket is new min --> new_bucket.next = self.min.next"
                min_old = self.min
                new_bucket = Bucket(None, None, counter)
                new_bucket.prev = min_old.prev
                new_bucket.next = min_old
                min_old.prev.next = new_bucket
                min_old.prev = new_bucket
                min_old.next.prev = new_bucket if min_old.next == min_old else min_old
                #print "so far so gppd"
                self.min = new_bucket


            self.elements[element] = counter

        else :
            #print "element not monitored and Stream Summary full"
            # element not monitored and Stream Summary full
            counter = Counter(element, None)
            if (self.min.next.value == self.min.value + 1) :
                # insert element into self.min.next
                self.min.next.insert(counter)
            else :
                # next bucket has value > min.value+1 --> overwrite min

                fc = self.min.firstChild
                self.elements[self.min.firstChild] = None
                tmp = fc.next
                while tmp != fc :
                    self.elements[tmp] = None
                    tmp = tmp.next

                new_bucket = Bucket(self.min.prev, self.min.next, counter, value = (self.min.value + 1))
                self.min = new_bucket


            self.elements[element] = counter
        #print "finished adding;\n self.min ",str(self.min)
        #print "min.prev", str(self.min.prev)
        #print "min.next", str(self.min.next)

        #print "min.next.prev.", str(self.min.next.prev)
        #print "min.prev.next", str(self.min.prev.next)
    def getelements(self) :
        return self.elements

ss_size = 10
#stream = np.random.zipf(2.8, 1000000)
#stream = [ 1,1,1,1,1,1,1,1,1,1,5,1,1,1,1,1,1,1,5,1,1,2,1,1,2,18,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,2,1,4,1,2,1,1,1,3,1,1,1,3,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1
#,1,1,1,1,4,1,2,2,1,1,1,4,4,1,2,1,1,1,1,11,1,2,1,1,1]


#print (stream)

def callback(*args, **kwargs):
    print (args, kwargs)


with util.Timer() as t :
    ss = Stream_Summary(ss_size)

    for el in stream :
        ss.insert(el)
    #print "SS\n", ss
print('Summary took %.03f sec.' % t.interval)
print "SS result\n", ss
print ss.getelements().keys()